This section contains further exposition (including proofs) for Section 4. A.1 Limitations of utility difference as an instability measure But its utility difference remains at 0. Minimum stabilizing subsidy equals Subset Instability for any market outcome. This is no larger than Subset Instability by definition. Let's take the maximum weight matching of We first formally define the unhappiness of a coalition, as follows. Recall that, in terms of unhappiness, Proposition 4.3 is as follows: Proposition 4.3. By Proposition 4.2, we know that Subset Instability is equal to Thus, it suffices to prove that the maximum unhappiness of any coalition is equal to (7).

Algorithmically, we show that "optimism in the face of uncertainty," the principle underlying many bandit algorithms, applies to a primal-dual formulation of matching with transfers and

Large-scale, two-sided matching platforms must find market outcomes that align with user preferences while simultaneously learning these preferences from data. However, since preferences are inherently uncertain during learning, the classical notion of stability (Gale and Shapley, 1962; Shapley and Shubik, 1971) is unattainable in these settings. To bridge this gap, we develop a framework and algorithms for learning stable market outcomes under uncertainty. Our primary setting is matching with transferable utilities, where the platform both matches agents and sets monetary transfers between them. We design an incentive-aware learning objective that captures the distance of a market outcome from equilibrium. Using this objective, we analyze the complexity of learning as a function of preference structure, casting learning as a stochastic multi-armed bandit problem. Algorithmically, we show that "optimism in the face of uncertainty," the principle underlying many bandit algorithms, applies to a primal-dual formulation of matching with transfers and leads to near-optimal regret bounds. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.